import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author hewei
 * @version 1.0
 * @description: 1130. 叶值的最小代价生成树
 * 这个题目的本质就是将数组中的数两两配对，配对指的是相乘，将相乘之后的数加到ans中，同时将两个数中最大的数留在数组中，直到数组中只有一个数为止，求ans的最小值
 * @date 2022/11/18 16:24
 */

public class MctFromLeafValues {

    public static void main(String[] args) {
        int[] arr = {6,2,4};
        System.out.println(new MctFromLeafValues().mctFromLeafValues(arr));
    }

    int[][] max;
    int[][] dp;
    public int mctFromLeafValues1(int[] arr) {
        int n = arr.length;
        max = new int[n][n];
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            int temp = 0;
            Arrays.fill(dp[i], 0);
            for (int j = i; j < n; j++) {
                max[i][j] = Math.max(temp, arr[j]);
                temp = max[i][j];
            }
        }
        return process(0, arr.length - 1);
    }

    public int process(int l, int r) {
        if (l > r) {
            return -1;
        }
        if (dp[l][r] != 0) return dp[l][r];
        if (l == r) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = l; i < r; i++) {
            int maxL = max[l][i], maxR = max[i + 1][r];
            int processL = process(l, i);
            int processR = process(i + 1, r);
            ans = Math.min(ans, processL + processR + maxL * maxR);
        }
        dp[l][r] = ans;
        return ans;
    }

    public int mctFromLeafValues2(int[] arr) {
        int n = arr.length;
        int[][] max = new int[n][n];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            int temp = 0;
            Arrays.fill(dp[i], 0);
            for (int j = i; j < n; j++) {
                max[i][j] = Math.max(temp, arr[j]);
                temp = max[i][j];
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int res = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    res = Math.min(res, dp[i][k] + dp[k + 1][j] + max[i][k] * max[k + 1][j]);
                }
                dp[i][j] = res;
            }
        }
        return dp[0][n - 1];
    }

    public int mctFromLeafValues(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offerFirst(Integer.MAX_VALUE);
        int ans = 0;
        for (int i : arr) {
            while (i >= stack.peekFirst()) {
                ans += stack.pollFirst() * Math.min(i, stack.peekFirst());
            }
            stack.offerFirst(i);
        }
        while (stack.size() > 2) {
            ans += stack.pollFirst() * stack.peekFirst();
        }
        return ans;
    }
}
